package org.example.algorithm.dp;
//1981. 最小化目标值与所选元素的差
//todo:dp优化内存占用

public class MinimizeTheDifferenceSolution {
    private int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        int[][] mat = {{3,5}, {5,10}};
        int target = 47;
        MinimizeTheDifferenceSolution solution = new MinimizeTheDifferenceSolution();
        int res = solution.minimizeTheDifference(mat, target);
        System.out.println(res);
    }

    public int minimizeTheDifference(int[][] mat, int target) {
        int maxSum = mat.length * 70;
        boolean[][] dp = new boolean[mat.length+1][maxSum+1];
        dp[0][0] = true;
        for (int i=1;i<=mat.length;i++) {
            for (int k=0;k<mat[i-1].length;k++) {
                for (int j=mat[i-1][k];j<=maxSum;j++) {
                    dp[i][j] = dp[i][j] || dp[i-1][j-mat[i-1][k]];
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i=1;i<=maxSum;i++) {
            if (dp[mat.length][i]) {
                min = Math.min(min, Math.abs(i - target));
            }
        }
        return min;
    }

    //dfs方式超出时间限制
    public int minimizeTheDifference2(int[][] mat, int target) {
        int[] minNum = new int[mat.length];
        for (int i=0;i<mat.length;i++) {
            minNum[i] = min;
            for (int j=0;j<mat[i].length;j++) {
                minNum[i] = Math.min(mat[i][j], minNum[i]);
            }
        }
        dfs(mat, 0, 0, target, minNum);
        return min;
    }

    private void dfs(int[][] mat, int index, int sum, int target, int[] minNum) {
        if (index == mat.length) {
            min = Math.min(min, Math.abs(target - sum));
            return;
        }
        int[] row = mat[index];
        if (sum >= target) {
            dfs(mat, index+1, sum+minNum[index], target, minNum);
        }  else {
            for (int num: row) {
                dfs(mat, index+1, sum+num, target, minNum);
            }
        }
    }
}
